/**
 *   @file MCTreeNode.cpp
 */
#include "MCTreeNode.h"
#include "MultiChildTree.h"
#include "../../common/UtilFuncT.h"
#include "../../common/CppMemPool.h"
#include "../../common/DLHook.h"
#include "../../exceptions/RuntimeException.h"
#include "../LinkedHashtableT.h"
#include "__internal/MCTreeHashtableList.h"

using namespace cppflib::exceptions;

namespace cppflib
{

namespace collections
{

namespace tree
{

/**
 *  @return our custom hash table
 */
PRIVATE MCTreeNodeLinkedHashtable * __GetLinkedHashtable(BaseObject * pChildList)
{
   return static_cast<MCTreeNodeLinkedHashtable *>(pChildList);
}

/**
 *  @return our custom list
 */
PRIVATE MCListT<MCTreeNode> * __GetList(BaseObject * pChildList)
{
   return static_cast<MCListT<MCTreeNode> *>(pChildList);
}

MCTreeNode::MCTreeNode(void)
{
   this->pKey = NULL;
   this->pParent = NULL;
   this->pMCTree = NULL;
   this->pChildList = NULL;
   this->pListHook = NULL;
}

PRIVATE const u32_t NRHASHBUCKETS = 47;

/**
 *  Init with a key (usually it is a CFString) and the tree it will be attached to
 */
MCTreeNode::MCTreeNode(BaseObject *pKey)
{
   this->pKey = pKey;
   cppmempool::Retain(this->pKey);
   this->pParent = NULL;    // don't retain as it will lead to circular reference
   this->pMCTree = NULL;    // don't retain as it will lead to circular reference
   this->pChildList = NULL;
   this->pListHook = NULL;
}

MCTreeNode::~MCTreeNode(void)
{
   if (this->pKey)
      cppmempool::Release(this->pKey);

   this->DeleteAllChildren();
}

/**
 *  Get parent node
 */
MCTreeNode * MCTreeNode::GetParent()
{
   return this->pParent;
}

/**
 *  Get next sibling node
 *  
 *  @return next tree node (may be NULL)
 */
MCTreeNode * MCTreeNode::GetNextSibling()
{
   if (IsRootNode())  // root node should have no siblings
      return NULL;

   if (!pListHook)
      throw RuntimeException(_S("This node isn't attached to a tree yet"));

   if (cppflib::InstanceOf<MCTreeNodeLinkedHashtable>(pParent->pChildList)) {
      return __GetLinkedHashtable(pParent->pChildList)->GetNextValue(pListHook);  
   }

   return __GetList(pParent->pChildList)->GetNextElement(pListHook);
}

/**
 *  Get previous sibling node
 *
 *  @return previous tree node (may be NULL)
 */
MCTreeNode * MCTreeNode::GetPrevSibling()
{
   if (IsRootNode())  // root node should have no siblings
      return NULL;

   if (!pListHook)
      throw RuntimeException(_S("This node isn't attached to a tree yet"));

   if (cppflib::InstanceOf<MCTreeNodeLinkedHashtable>(pParent->pChildList)) {
      return __GetLinkedHashtable(pParent->pChildList)->GetPrevValue(pListHook);  
   }

   return __GetList(pParent->pChildList)->GetPrevElement(pListHook);
}

/**
 *  Get child by index
 */
MCTreeNode * MCTreeNode::GetChild(u32_t index)
{
   if (!pChildList)
      return NULL;

   if (cppflib::InstanceOf<MCTreeNodeLinkedHashtable>(pChildList)) {
      // a linked hash
      if (index >= __GetLinkedHashtable(pChildList)->GetCount()) 
         return NULL;

      const BaseObject *pTempKey = NULL;
      MCTreeNode *pTempVal = NULL;
      __GetLinkedHashtable(pChildList)->Get(static_cast<int>(index), pTempKey, pTempVal);
      return pTempVal;
   }

   // it is a list
   if (index >= __GetList(pChildList)->GetCount()) 
      return NULL;

   return __GetList(pChildList)->Get(static_cast<int>(index));
}

/**
 *  Get child by key. If this tree allows children with same key, the first matched child will be returned
 */
MCTreeNode * MCTreeNode::GetChild(const BaseObject &key)
{
   if (!pChildList)
      return NULL;

   if (cppflib::InstanceOf<MCTreeNodeLinkedHashtable>(pChildList)) {
      // a linked hash
      return __GetLinkedHashtable(pChildList)->Get(key);
   }

   // it is a list
   int listCount = static_cast<int>(__GetList(pChildList)->GetCount());
   for (int i = 0; i < listCount; ++i) { 
      MCTreeNode * pChildNode = __GetList(pChildList)->Get(i);
      if (pChildNode->GetKey()->Equals(key))
         return pChildNode;
   }

   return NULL;
}

/**
 *  Get tree attached
 */
MultiChildTree * MCTreeNode::GetAttachedTree()
{
   return pMCTree;
}

/**
 *  Get key of this node
 */
const BaseObject * MCTreeNode::GetKey()
{
   return pKey;
}

/**
 *  Get number of child count
 */
u32_t MCTreeNode::GetDirectChildCount()
{
   if (!pChildList)
      return 0;

   if (cppflib::InstanceOf<MCTreeNodeLinkedHashtable>(pChildList)) 
      return __GetLinkedHashtable(pChildList)->GetCount();

   return __GetList(pChildList)->GetCount();
}

/**
 *  Get child count recursively
 */
PRIVATE u32_t __GetAllChildCount(MCTreeNode &node)
{
   u32_t totalCount = 0;
   u32_t childCount = node.GetDirectChildCount();

   for (u32_t i = 0; i < childCount; ++i)
      totalCount += __GetAllChildCount(*node.GetChild(i));
   
   return childCount + totalCount;
}


/**
 *  Get all child count recursively down to leaves
 */
u32_t MCTreeNode::GetAllChildCount()
{
   return __GetAllChildCount(*this);  
}

/**
 *  Has parent or not
 */
bool MCTreeNode::HasNoParent()
{
   return (pParent == NULL);
}

/**
 *  Test if root node or not
 */
bool MCTreeNode::IsRootNode()
{
   if (!pMCTree)
      throw RuntimeException(_S("This node isn't attached to a tree yet"));

   return (pMCTree->GetRootNode() == this);
}

/**
 *  Get the depth of this node
 *  Root node is of depth zero.
 */
u32_t MCTreeNode::GetDepth()
{
   u32_t depth = 0;
   MCTreeNode *pTempParent = this->pParent;
   while (pTempParent != NULL) {
      ++depth;
      pTempParent = pTempParent->pParent;
   }

   return depth;
}

/**
 *  Add a child
 *
 *  @return false if uniqueChildKeyOnly is true and there is already a child with the same key
 */
bool MCTreeNode::AddChild(MCTreeNode * pChild)
{
   if (!pMCTree)
      throw RuntimeException(_S("This node isn't attached to a tree yet"));
 
   if (!pChild)
      return false;

   if (pChild->pMCTree || pChild->pParent || pChild->pListHook)
      throw RuntimeException(_S("Child node is already attached to a tree"));

   if (pChild->pChildList) {
      bool curTreeUniqueness = pMCTree->AllowUniqueChildKeyOnly();
      bool childUniqueness = cppflib::InstanceOf<MCTreeNodeLinkedHashtable>(pChild->pChildList);
      if (curTreeUniqueness != childUniqueness)
         throw RuntimeException(_S("The key uniqueness requirement of this tree and child nodes are different"));
   }

   if (!pChildList) {
      // allocate child list if not already have one
      if (pMCTree->AllowUniqueChildKeyOnly())
         pChildList = new MCTreeNodeLinkedHashtable(NRHASHBUCKETS);
      else
         pChildList = new MCListT<MCTreeNode>();
      cppmempool::Retain(pChildList);
   }

   cppflib::DLHook *pHook = NULL;
   if (pMCTree->AllowUniqueChildKeyOnly()) {
      if (__GetLinkedHashtable(pChildList)->ContainsKey(*pChild->GetKey()))
         return false;

      __GetLinkedHashtable(pChildList)->Set(pChild->pKey, pChild, pHook);   
   }
   else {
      __GetList(pChildList)->AddTail(pChild, pHook);
   }

   // post update
   pChild->SetAttachingTree(this->pMCTree);
   pChild->pParent = this;
   pChild->pListHook = pHook;

   return true;
}

/**
 *  Delete child by index
 */
bool MCTreeNode::DeleteChild(u32_t index)
{
   if (!pChildList)
      return false;

   if (cppflib::InstanceOf<MCTreeNodeLinkedHashtable>(pChildList)) {
      if (index >= __GetLinkedHashtable(pChildList)->GetCount())
         return false;

      __GetLinkedHashtable(pChildList)->RemoveAt(static_cast<int>(index));
   }
   else {
      if (index >= __GetList(pChildList)->GetCount())
         return false;

      __GetList(pChildList)->RemoveAt(static_cast<int>(index));
   }
   
   return true;
}

/**
 *  Delete child by key. If this tree allows children with same key, the first matched child will be deleted
 */
bool MCTreeNode::DeleteChild(const BaseObject &key)
{
   if (!pChildList)
      return false;

   if (cppflib::InstanceOf<MCTreeNodeLinkedHashtable>(pChildList)) {
      return __GetLinkedHashtable(pChildList)->Remove(key);
   }
   else {
      int listCount = static_cast<int>(__GetList(pChildList)->GetCount());
      for (int i = 0 ; i < listCount; ++i) {
         if (__GetList(pChildList)->Get(i)->GetKey()->Equals(key)) {
            __GetList(pChildList)->RemoveAt(i);
            return true;
         }
      }
   }
   
   return false;
}

/**
 *  Delete all children
 */
void MCTreeNode::DeleteAllChildren()
{
   if (pChildList) {
      cppmempool::Release(pChildList);
      pChildList = NULL;
   }
}


/**
 *  Check if node passed in is one of its ancestor
 */
bool MCTreeNode::IsAncestor(MCTreeNode *pNode)
{
   if (!pNode)
      return false;

   MCTreeNode *pTempParent = this->pParent;
   while (pTempParent != NULL) {
      if (pTempParent == pNode)
         return true;

      pTempParent = pTempParent->pParent;
   }

   return false;
}

/**
 *  Move itself to the child of another node of the same tree
 */
bool MCTreeNode::Move(MCTreeNode *pNode)
{
   if (IsRootNode())   // can't move root
      return false;

   // can't move to a different tree
   if (!pNode || pNode->pMCTree != this->pMCTree)  
      return false;

   if (this == pNode)  // can't move to itself
      return false;

   if (this->pParent == pNode)   // already a child of the target node
      return false;   
   
   if (pNode->IsAncestor(this))  // can't move to its descendant
      return false;

   MCTreeNode *orgParent = this->pParent;
   cppflib::DLHook *orgHook = this->pListHook;
   
   ClearParentAndTree(); // clear first
   
   if (!pNode->AddChild(this))
      return false;   
   
   // unlink itself from original parent
   if (cppflib::InstanceOf<MCTreeNodeLinkedHashtable>(orgParent->pChildList)) {
      __GetLinkedHashtable(orgParent->pChildList)->Remove(*this->pKey);
   }
   else {
      __GetList(orgParent->pChildList)->Remove(orgHook);
   }

   return true;
}

/**
 *  Clear the pMCTree pointer of this node and all its children
 */
void MCTreeNode::ClearAttachingTree()
{
   if (pChildList) {

      if (cppflib::InstanceOf<MCTreeNodeLinkedHashtable>(pChildList)) {
         const BaseObject *pKey;
         MCTreeNode *pNode;
         for (int i = 0; i < static_cast<int>(__GetLinkedHashtable(pChildList)->GetCount()); ++i) {
            __GetLinkedHashtable(pChildList)->Get(i, pKey, pNode);
            pNode->ClearAttachingTree();
         }
      }
      else {
         for (int i = 0; i < static_cast<int>(__GetList(pChildList)->GetCount()); ++i) {
            MCTreeNode *pNode = __GetList(pChildList)->Get(i);
            pNode->ClearAttachingTree();
         }
      }
   }

   this->pMCTree = NULL; // clear myself
}

/**
 *  Set the pMCTree pointer of this node and all its children
 */
void MCTreeNode::SetAttachingTree(MultiChildTree *pMCTree)
{
   if (pChildList) {

      if (cppflib::InstanceOf<MCTreeNodeLinkedHashtable>(pChildList)) {
         const BaseObject *pKey;
         MCTreeNode *pNode;
         for (int i = 0; i < static_cast<int>(__GetLinkedHashtable(pChildList)->GetCount()); ++i) {
            __GetLinkedHashtable(pChildList)->Get(i, pKey, pNode);
            pNode->SetAttachingTree(pMCTree);
         }
      }
      else {
         for (int i = 0; i < static_cast<int>(__GetList(pChildList)->GetCount()); ++i) {
            MCTreeNode *pNode = __GetList(pChildList)->Get(i);
            pNode->SetAttachingTree(pMCTree);
         }
      }
   }

   this->pMCTree = pMCTree; // assign to myself
}

/**
 *  Simply clear parent and tree pointer
 */
void MCTreeNode::ClearParentAndTree()
{
   this->pMCTree = NULL;
   this->pParent = NULL;
   this->pListHook = NULL;
}

/**
 *  Detach itself from the attaching tree.
 *  All its children will have their attaching tree cleared but parent remained the same.
 *
 */
void MCTreeNode::DetachFromTree()
{
   if (!pMCTree || !pParent || !pListHook)
      return;

   ClearAttachingTree();

   int refCount = cppmempool::Retain(this); // in case Remove below may destroy this node
   
   // unlink itself from parent (reference count will be decremented by 1)
   if (cppflib::InstanceOf<MCTreeNodeLinkedHashtable>(pParent->pChildList)) {
      __GetLinkedHashtable(pParent->pChildList)->Remove(*this->pKey);
   }
   else {
      __GetList(pParent->pChildList)->Remove(pListHook);
   }

   ClearParentAndTree(); // clear these at the end

   if (refCount > 2) {
      cppmempool::Release(this); //  to cancel the effect of Retain above so that caller don't need 
                                 //+ to call Release manually after this method
   }
   else if (refCount == 2) {
      cppmempool::AddToCurPool(this);  // this node is not attached to any memory pool
   }
}


}  // end of namespace tree

}  // end of namespace collections

}  // end of namespace cppflib

